#include "graph.h"
#include "BinarySearchTree.h"
#include <iostream>
#include <cstdlib>

template<typename T>
T* Dijkstra_all(Graph<T> G, int point);

template<typename T>
T* Dijkstra_all(Graph<T> G, int point, BinaryTree<T>* _path);

template<typename T>
T Dijkstra(Graph<T> G, int point_1, int point_2);


template<typename T>
T* Dijkstra_all(Graph<T> G, int point){
  LinkedList<T>* L = G.adj_list();
  T* S = new T(G.get_point()+1);
  BinaryTree<T> Q;
  Q.insert(point,0);
  for (int i=1; i<=G.get_point() ; i++){
    if (i != point)
      Q.insert(i,inf);
  }
  int u = 0;
  while (Q.isempty() != 1){
    TNode<T>* x = Q.min();
    u = x->point;
    Node<T>* tail = L[u].get_head();
    if (tail != NULL){
      while (tail->get_next() != NULL){
	TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
	  tail = tail->get_next();  
      }
      TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
   }
	S[u] = x->data;
	Q.del(x);
  }
      return S;
}

template<typename T>
T* Dijkstra_all(Graph<T> G, int point, BinaryTree<T>* _path){
 LinkedList<T>* L = G.adj_list();
  T* S = new T(G.get_point()+1);
  BinaryTree<T> Q;
  Q.insert(point,0);
  for (int i=1; i<=G.get_point() ; i++){
    if (i != point)
      Q.insert(i,inf);
  }
  BinaryTree<T>* Path = new BinaryTree<T>;
  Path->insert(point,0);
  int u = 0;
  while (Q.isempty() != 1){
    TNode<T>* x = Q.min();
    u = x->point;
    TNode<T>* z = Path->find(u);
    Node<T>* tail = L[u].get_head();
    if (tail != NULL){
      while (tail->get_next() != NULL){
	TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    TNode<T>* w = Path->find(npoint);
	    if (w == NULL)
	      w = new TNode<T>(npoint,ndata);
	    Path->set_parent(z,w);
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
	  tail = tail->get_next();  
      }
      TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    TNode<T>* w = Path->find(npoint);
	    if (w == NULL)
	      w = new TNode<T>(npoint,ndata);
	    Path->set_parent(z,w);
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
   }
	S[u] = x->data;
	Q.del(x);
  }
      _path = Path;
      return S;
}


template<typename T>
T Dijkstra(Graph<T> G, int point_1, int point_2){
   LinkedList<T>* L = G.adj_list();
  T* S = new T(G.get_point()+1);
  BinaryTree<T> Q;
  Q.insert(point_1,0);
  for (int i=1; i<=G.get_point() ; i++){
    if (i != point_1)
      Q.insert(i,inf);
  }
  int u = 0;
  while (Q.isempty() != 1){
    TNode<T>* x = Q.min();
    u = x->point;
    Node<T>* tail = L[u].get_head();
    if (tail != NULL){
      while (tail->get_next() != NULL){
	TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
	  tail = tail->get_next();  
      }
      TNode<T>* y = Q.find(tail->get_end());
	if (y != NULL && y->data > x->data + tail->get_weight()){
	    int npoint = y->point;
	    T ndata = x->data + tail->get_weight();
	    Q.del(y);
	    Q.insert(npoint,ndata);
	}
   }
	S[u] = x->data;
	if (u == point_2)
	  break;
	Q.del(x);
  }
      return S[u];
}


